#include <string.h>
#include <stdlib.h>
#include "hash.h"
#include "lista.h"
#include "vector_dinamico.h"

#include <stdio.h>

#define TAM 100
#define MAX 200	

/* *********************************************************************
 * 			DECLARACION DE LOS TIPOS DE DATO
 * ********************************************************************/

typedef struct _dato {
	
	char* clave;
	void* valor;
	
}dato_t;

struct hash{
	
	vector_t *vector;
	/* Invariante cantidad. LLeva la cuenta de la cantidad de datos
	 *  que tiene guardados la tabla de hash */
	size_t cantidad; 
	/* Invariante que mantiene la maxima cantidad de datos antes de 
	 * una redimension */
	size_t maximo;
	hash_destruir_dato_t destruir_dato; 

};

struct hash_iter{
	
	size_t pos;
	lista_iter_t *iter;
	const hash_t *hash; 
};

/* *********************************************************************
 * 	 				FUNCION DE HASH
 * ********************************************************************/

size_t fhash (const char* clave, size_t cant){
	
	size_t indice = 0;

	for (int i = 0; i<strlen (clave) ; i++){
		
		indice += clave[i]*(10*i);  

		char corr = clave [i] << 3;
	
		indice += corr ^ clave[i];  
	}
	
	indice %= cant;

	return indice; 
	
}

/* *********************************************************************
 * 				    IMPLEMENTACION
 * ********************************************************************/

dato_t* dato_crear (const char* clave, void* valor){
	
	/* Pido memoria para el nuevo dato */
	dato_t *nuevo_dato = malloc (sizeof(dato_t));
	if (!nuevo_dato) /* Control de errores */
		return NULL;
	
	/* Pido memoria para la clave y la copio */
	nuevo_dato->clave = malloc ((strlen(clave)+1)*sizeof(char));
	if (!nuevo_dato->clave){ /* Control de errores */
		free (nuevo_dato);
		return NULL;
	}
	strcpy (nuevo_dato->clave,clave);
	
	nuevo_dato->valor = valor;
	
	/* Devuelvo el dato */
	return nuevo_dato;

}

char* dato_mostrar_clave (const dato_t *dato){
	
	/* Verifico que exista el dato pasado como parametro */
	if (!dato)
		return NULL;
		
	return dato->clave;
	
}

void* dato_mostrar_valor (const dato_t *dato){
	
	/* Verifico que exista el dato pasado como parametro */
	if (!dato)
		return NULL;
		
	return dato->valor;
	
}

void dato_destruir (dato_t* dato, hash_t* hash){
	
	free(dato->clave);
	if (hash->destruir_dato)
			hash->destruir_dato(dato->valor);
	free(dato);
	
}

bool hash_guardar_dato (hash_t* hash, dato_t* dato){
	
	/* Obtengo la lista donde tengo que ingresar la nueva clave */	
	size_t tamanio = vector_obtener_tamanio (hash->vector);
	lista_t* lista = vector_obtener (hash->vector,fhash(dato->clave,tamanio));
	
	/* Si no existe la lista, la creo */
	if (!lista){
		lista = lista_crear ();
		if (!lista){ /* Control de errores */
			dato_destruir(dato,hash);
			return false;
		}
		/* Guardo la lista en el vector */	
		if (!vector_guardar (hash->vector,fhash(dato->clave,tamanio),lista)){
			dato_destruir(dato,hash);
			vector_guardar (hash->vector,fhash(dato->clave,tamanio),NULL);
			return false;
		}
	}
	
		
	/* Controlo que el dato se ha insertado correctamente */
	if (!lista_insertar_primero (lista,dato)){
		dato_destruir(dato,hash);
		if (lista_esta_vacia (lista)){
			lista_destruir (lista,NULL);
			vector_guardar (hash->vector,fhash(dato->clave,tamanio),NULL);
		}
		return false;
	}
	
	hash->cantidad++;
	
	return true;
	
}

bool hash_rehash(hash_t *hash,vector_t *vector_viejo){
	
	for (int i=0 ; i<vector_obtener_tamanio (vector_viejo) ; i++){
	
		/* Obtengo la lista en la posicion i */
		lista_t* lista = vector_obtener (vector_viejo, i);
		if (!lista) continue;
		
		lista_iter_t *iter = lista_iter_crear (lista);
		if (!iter)
			return false;
		
		while (!lista_iter_al_final (iter)){
			
			dato_t* dato = lista_iter_ver_actual (iter);
			if (!dato){ /* Control de errores */
				lista_iter_destruir (iter);
				return false;
			}
			
			if (!hash_guardar_dato(hash,dato)){
				lista_iter_destruir (iter);
				return false;
			}
				
			if (!lista_iter_avanzar (iter)){
				lista_iter_destruir (iter);
				return false;
			}
			
		}
		
		lista_iter_destruir (iter);	
		
	}
	
	
	
	return true;
	
	
}

bool hash_redimensionar (hash_t *hash,size_t tam){
	
	vector_t *nuevo_vector = vector_crear (tam);
	if (!nuevo_vector) /* Control de errores */
		return false;
		
	/* Inicializo el nuevo vector en NULL */
	for (int i=0 ; i<tam ; i++)
		vector_guardar (nuevo_vector,i,NULL);
	
	vector_t *vector_viejo = hash->vector;
	size_t cant_anterior = hash->cantidad;
	
	hash->cantidad = 0;
	hash->vector = nuevo_vector;
	hash->maximo = 2*vector_obtener_tamanio (hash->vector);
	
	size_t nuevo_tamanio = vector_obtener_tamanio (hash->vector);
		
	if (!hash_rehash (hash,vector_viejo)){ /* Control de error en el rehash */
		for (int j=0 ; j<nuevo_tamanio ; j++){
			lista_t *lista = vector_obtener (hash->vector,j);
			if (!lista)
				continue;
			
			lista_destruir (lista,NULL);
		}
		
		vector_destruir (hash->vector, NULL);
		/* Vuelvo a asignar el vector viejo */
		hash->vector = vector_viejo;
		hash->cantidad = cant_anterior;
		hash->maximo /= 2;
		
		return false;
	}
		
	
	size_t viejo_tamanio = vector_obtener_tamanio (vector_viejo);		
	/* Destruyo el vector viejo */
	for (int x=0 ; x<viejo_tamanio ; x++){
		lista_t *lista = vector_obtener (vector_viejo,x);
		if (lista)
			lista_destruir (lista,NULL);
	}
	vector_destruir (vector_viejo,NULL);
	
	return true;
	
}

hash_t* hash_crear (hash_destruir_dato_t destruir_dato){
	
	/* Creo la nueva tabla de Hash */
	hash_t *nuevo_hash = malloc (sizeof(hash_t));
	if (!nuevo_hash) /* Control de errores */
		return NULL;
		
	/* Inicializo los campos */
	/* Creo el vector */
	nuevo_hash->vector = vector_crear (TAM);
	if (!nuevo_hash->vector){ /* Control de errores */
		free (nuevo_hash);
		return NULL;
	}
	
	/* Inicializo los campos del vector en NULL */
	for (int i=0 ; i<TAM ; i++)
		vector_guardar (nuevo_hash->vector,i,NULL);
	
	/* Inicializo la cantidad */
	nuevo_hash->cantidad = 0;
	
	/* Inicializo el maximo */
	nuevo_hash->maximo = MAX;
	
	/* Inicializo la funcion destruir_dato */
	nuevo_hash->destruir_dato = destruir_dato;
	
	return nuevo_hash;
	
}

bool hash_guardar (hash_t *hash, const char* clave, void* valor){
	
	if (hash_pertenece (hash,clave)){
		void* valor = hash_borrar (hash,clave);
		if (!valor)
			return false;
		if (hash->destruir_dato)
			hash->destruir_dato (valor);	
	}
	
	
	/* Creo el dato */
	dato_t* dato = dato_crear (clave,valor);
	if (!dato) /* Control de errores */
		return false;	
	
	if (!hash_guardar_dato (hash,dato))
		return false;
	
	 /* Condicion de redimension */
	size_t tamanio = vector_obtener_tamanio (hash->vector); 
	if (hash->cantidad > hash->maximo)
		hash_redimensionar (hash, 4*tamanio);
		
	
	return true;
	
}

void *hash_borrar(hash_t *hash, const char *clave){
	
	/* Obtengo la lista donde debería estar el dato asociado a 
	 * la clave pasada como parametro */
	size_t tamanio = vector_obtener_tamanio (hash->vector);
	lista_t *lista = vector_obtener (hash->vector,fhash(clave,tamanio));
	
	/* Si la lista no fue creada (NULL) quiere decir que el dato no
	 * se encuentra el el hash. Devuelvo NULL. */
	if (!lista)	return NULL;
	
	/* Creo un iterador para buscar la clave en la lista */
	lista_iter_t *iter = lista_iter_crear (lista);
	/* Control de errores */
	if (!iter) 	return NULL;
	
	/* Recorro la lista con el iterador buscando la clave */
	while (!lista_iter_al_final(iter)){
		char* clave_dato = dato_mostrar_clave(lista_iter_ver_actual(iter));
		if (strcmp(clave_dato,clave) == 0)
			break;
		lista_iter_avanzar (iter);
	}
	
	/* Si el iterador se encuentra al final de la lista, significa
	 * que no se encontro la clave durante la iteracion */
	if (lista_iter_al_final (iter)){
		lista_iter_destruir (iter);
		return NULL;
	}
	
	/*extraigo de la lista el dato*/
	dato_t *dato = lista_borrar(lista,iter); 
	
	if (lista_esta_vacia (lista)){
		lista_destruir (lista, NULL);
		vector_guardar (hash->vector,fhash(clave,tamanio),NULL);
	}
	
	lista_iter_destruir (iter);
	
	void* valor = dato_mostrar_valor (dato);
	
	free (dato->clave);
	free (dato);
	
	hash->cantidad--;
	
	/* Condicion de redimension */
	if (hash->cantidad < hash->maximo/8 && hash->maximo > MAX)
		hash_redimensionar (hash, tamanio/2);
	
	return valor;
	
}

dato_t* hash_obtener_dato (const hash_t *hash, const char *clave){
	
	/* Obtengo la lista donde debería estar el dato asociado a 
	 * la clave pasada como parametro */
	lista_t *lista = vector_obtener
	(hash->vector,fhash (clave,vector_obtener_tamanio (hash->vector)));
	
	/* Si la lista no fue creada (NULL) quiere decir que el dato no
	 * se encuentra el el hash. Devuelvo false. */
	if (!lista)
		return NULL;
	
	/* Creo un iterador para buscar la calve en la lista */
	lista_iter_t *iter = lista_iter_crear (lista);
	if (!iter) /* Control de errores */
		return NULL;
	
	/* Recorro la lista con el iterador buscando la clave */
	while (!lista_iter_al_final(iter)){ 
		char* clave_dato = dato_mostrar_clave(lista_iter_ver_actual(iter)); 
		if (strcmp(clave_dato,clave) == 0)
			break;
		if (!lista_iter_avanzar (iter))
			break;
	}
		
	/* Si el iterador se encuentra al final de la lista, significa
	 * que no se encontro la clave durante la iteracion */
	if (lista_iter_al_final (iter)){
		lista_iter_destruir (iter);
		return NULL;
	}
	
		
	/* Si la lista no esta al final, significa que antes de
	 * llegar al final se encontro una clave coincidente */
	 dato_t* dato = lista_iter_ver_actual (iter);
	 if (!dato) /* Control de errores */
		return false;
	 
	 /* Destruyo el iterador*/
	lista_iter_destruir (iter);
	
	return dato;
	
}

void *hash_obtener(const hash_t *hash, const char *clave){
	
	
	/* Obtengo el dato que deseo */
	dato_t* dato = hash_obtener_dato (hash,clave);
	if (!dato) /* Control de errores */
		return false;
			
		
	return dato_mostrar_valor(dato);
	
	
}

bool hash_pertenece (const hash_t *hash,const char *clave){
	
	/* Si no puedo obtener el elemento que se busca, devuelvo false */
	if (!hash_obtener (hash,clave))
		return false;
		
	/* Si devuelve un elemento, devuelvo true */
	return true;

}

size_t hash_cantidad(const hash_t *hash){
	
	return hash->cantidad;
	
}

void hash_destruir (hash_t *hash){
	
	size_t tamanio = vector_obtener_tamanio (hash->vector);
	
	/* Destruyo las listas y lo que contienen */
	for (int i=0 ; i<tamanio ; i++){
		/* Obtengo el dato de la posicion i */
		lista_t* lista = vector_obtener (hash->vector,i);
		/* Si hay una lista en la posicion i, la destuyo iterandola */
		if (!lista)
			continue;
			
		while (!lista_esta_vacia(lista)){
				
			void* elemento = lista_borrar_primero(lista);
			dato_destruir(elemento,hash);
				
		}
		
		lista_destruir(lista,NULL);
		
	}		
	
	/* Destruyo el vector */
	vector_destruir (hash->vector,NULL);
	
	/* Destruyo la tabla de hash */
	free (hash);
	
}

/* *********************************************************************
 * 							ITERADORES
 * ********************************************************************/

hash_iter_t *hash_iter_crear(const hash_t *hash){
	
	/* Pido memoria para el nuevo iterador */
	hash_iter_t *iter = malloc(sizeof(hash_iter_t));
	
	 /* Control de errores */
	if (!iter) return NULL;
	
	/* Inicialización del iterador */	
	iter->pos = 0;
	iter->hash = hash;
	iter->iter = NULL;
	
	/*si esta vacio que lo devuelva como esta*/
	if (hash_cantidad (hash) == 0) return iter;
	
	/*sino que apunte a su primer elemento*/	
	if (!hash_iter_avanzar(iter)) return NULL;

	/* Devuelvo el iterador creado */
	return iter;
}


bool hash_iter_avanzar(hash_iter_t *iter){
	
	/*verifica que no se haya terminado el hash*/
	if (hash_iter_al_final(iter))
		 return false;
	
	
	/*si el iterador no apunta a una lista le busca una*/
	if (!iter->iter){
	
		/*avanzo hasta encontrar una lista*/
		while ((!vector_obtener (iter->hash->vector,iter->pos)) 
			&& (iter->pos < (vector_obtener_tamanio(iter->hash->vector) -1)))
				iter->pos++;
		
		/*si no encuentro, es que no hay mas*/
		if (!vector_obtener (iter->hash->vector,iter->pos)) return false;
		
		/*creo un iterador en la lista encontrada*/
		iter->iter = lista_iter_crear(vector_obtener (iter->hash->vector,iter->pos));
		
		/*regreso con true*/
		return true;
	}
	
	/*si llega al final, cambia de lista*/
	if (lista_iter_al_final(iter->iter)){
		
		/*destruyo el viejo*/
		lista_iter_destruir(iter->iter);
		iter->iter = NULL;
		
		/*avanzo y vuelvo a empezar*/
		iter->pos++;

		if (!hash_iter_avanzar(iter)){
			 return false;
		}
	}else{
		
		/*si esta en una lista que tiene mas elementos avanza*/
		lista_iter_avanzar(iter->iter);
	}

	
	/*si esta al final de una lista, que no sea la ultima, avanza*/
	if ((lista_iter_al_final(iter->iter)))	
		return hash_iter_avanzar(iter);
	
	/* Regreso con true */
	return true;
}


const char *hash_iter_ver_actual(const hash_iter_t *iter){
	
	/*se fija que haya algo*/
	if (hash_cantidad (iter->hash) == 0) return NULL;
	/* devuelve */	
	if (!iter->iter) return NULL;
	/*guarda el dato*/
	dato_t *dato = lista_iter_ver_actual(iter->iter);
	if (!dato)
		return NULL;
	/*devuelve la clave*/
	return dato->clave;
}
	

bool hash_iter_al_final(const hash_iter_t *iter){
	
	/*se fija que haya algo*/
	if (hash_cantidad (iter->hash) == 0) return true;
	/*se fija que este en el ultimo lugar*/
	if (iter->pos == (vector_obtener_tamanio(iter->hash->vector)-1)){
		/*se fija si es NULL*/
		if ((!iter->iter)) return true; 
		/* o si esta al final de la ultima lista*/
		if(lista_iter_al_final(iter->iter)) return true;
	}
	/*y sino, false*/
	return false;
}


void hash_iter_destruir(hash_iter_t* iter){
	
	/*destruyo & libero*/
	lista_iter_destruir(iter->iter);
	free(iter);
	
}
